For centuries, maze and labyrinth patterns have been manually created as artistic designs, religious symbols, and intellectual puzzles. Due to their high geometric complexity, large and intricate maze and labyrinth patterns are time consuming to produce manually. Accordingly, various computer implemented methods have been developed to assist in the creation of such patterns.
U.S. Pat. No. 6,347,995 describes the construction of a maze on a discrete rectangular grid. Two grid blocks are marked start and end by a user. The system then generates a random trunk path connecting start and end blocks. U.S. Pat. No. 4,718,017 presents similar techniques for generating mazes on a 2D grid of cells. The mazes are formed by marking each cell in the grid as either a wall or a path (black or white). Thus, the paths are restricted to follow the cells of a grid. When projected to the surface of a 3D object, however, the grid often must be stretched, sometimes severely distorting the pattern.
U.S. Pat. No. 5,831,633 describes a technique for generation of complex fractal imagery. In a “drawing process” the user specifies a “template”, i.e. a series of curve segments. Individual segments are then replaced with a transformed copy of the template in a recursive process that is a generalization of Mandelbrot's original algorithm. The end result is the “shape” of a fractal. In a “colorization” process the user controls the coloring of the fractal with the help of a “color path” that is specified as part of the template. Though the coloring process is independent of the drawing process, they both use the same iterative process. The technique does not produce mazes or labyrinths.
U.S. Pat. No. 6,968,255 describes a fractal technique for generating decorative curve patterns for applications related to embroidery. The inputs to the algorithm are a closed 2D boundary curve and a fractal shape (i.e., a pathway/curve with associated rules for fractal generation). The algorithm then iteratively applies the fractal axioms to the pathway. The resulting fractal curve is then smoothed and clipped to the boundary curve. Fractal techniques such as this one start out with a template and iteratively replace parts of the template with transformed copies of the template in a deterministic process.
U.S. Pat. No. 6,804,573 deals with the automatic creation of embroidery information from an image. The image is first segmented into closed regions (called objects) based on color posterization. Thin objects are those which can be approximated by a constant offset thickness around skeletal curves. The skeletal curves or medial axis of the thin object is thus computed and a constant thickness stitch defined along it. Thick objects are fragmented into sub-regions that are monotonic with respect to a given stitch angle (so that they can be stitched in runs). A stitch ordering over the parts is also defined to minimize thread cuts as the needle moves from part to part. The technique involves no evolution of a pattern toward increasing geometric complexity, and does not produce a maze or labyrinth.
U.S. Pat. No. 5,602,943 discloses a method to produce a monochrome image from a grayscale or color image by first defining a traversal pattern based on a space-filling curve. Each point on the curve corresponds to a cluster of pixels of the image. The cluster is evaluated for intensity and used to generate an equivalent set monochromatic pixels. The space filling curves are picked from a standard set Hilbert, Peano or Sierpinski curves at a fixed level of subdivision globally determined by the image. The curves do not evolve.